public class Sort {
    //时间复杂度O(N^2)
    //空间复杂度0(1)
    //不稳定
    public  void swap(int[] array,int i,int j) {
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }
    public  void selectsort(int[] array) {
        for(int i=0;i<array.length;i++){
            int minIndex=i;
            for(int j=i+1;j<array.length;j++){
                if(array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            swap(array,i,minIndex);

        }

    }
    public void HeapSort(int[] array){
        //1.创建大根堆
        //2.讲堆顶元素放入最后
       for(int parenet=(array.length-1-1)/2;parenet>=0;parenet--){
           create(array,parenet,array.length);
           //从上往下创建，array.length是判断是否调整好的条件.
       }
       paixu_heap(array);
    }
    //相当于从上往下创建大根堆，tmp相当于是判断是否调整好的条件。
    private void create(int[] array,int parent,int tmp) {
        int child=2*parent+1;
        while(child<tmp){
            //找左右子树最大值
            if(child+1<tmp&&array[child]<array[child+1]){
                child++;
            }
            if(array[child]>array[parent]){
                swap(array,child,parent);
                parent=child;
                child=2*parent+1;
            }else{
                break;
            }
        }

    }
    public void paixu_heap(int[] array){
        int end=array.length-1;
        while(end>0){
            swap(array,0,end);
            create(array,0,end);
            end--;
        }
    }
    public void bubblesort(int[] array){
        for(int i=0;i<array.length-1;i++){
            boolean flg=false;
            for(int j=0;j<array.length-1-i;j++){
                if(array[j]>array[j+1]){
                    swap(array,j,j+1);
                    flg=true;
                }
            }
            if(!flg){
                break;
            }
        }
    }
    public void quicksort(int[] array){
        quick(array,0,array.length-1);

    }

    private void quick(int[] array, int start, int end) {
        //1.递归终止条件
        if(start>=end){
            return;
        }
        //进行优化,越排越有序,当递归的时候，小于一个值了，就直接使用直接插入，终止递归
        if(end-start+1<=3){
            zhijiecharu(array,start,end);
            return;
        }
        //利用三数取中法优化，使得尽可能均匀分布
        int mid=getMin(array,start,end);
        swap(array,start,mid);
        int pivot=wakong(array,start,end);
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);

    }

    private int getMin(int[] array, int left, int right) {
        int mid=(left+right)/2;
        if(array[left]<array[right]){
            if(array[mid]>array[right]){
                return right;
            }else if(array[mid]<array[left]){
                return left;
            }else{
                return mid;
            }
        }else{
            if(array[mid]>array[left]){
                return left;
            }else if(array[mid]<array[right]){
                return right;
            }else{
                return mid;
            }
        }

    }

    private void zhijiecharu(int[] array, int start, int end) {
        for(int i=start+1;i<=end;i++){
            int tmp=array[i];
            int j=i-1;
            for(;j>=start;j--){
                if(array[j]>array[i]){
                    array[i]=array[j];
                }else{
                    array[i]=tmp;
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }

    private int wakong(int[] array, int left, int right) {
        int tmp=array[left];
        while(left<right){
            while(left<right&&array[right]>=tmp){
                right--;
            }
            array[left]=array[right];
            while(left<right&&array[left]<=tmp){
                left++;
            }
            array[right]=array[left];
        }
        array[left]=tmp;
        return left;
    }
    public void jishupaixu(int[] array){
        //1.找待排序数组中的最大值和最小值
         int max=array[0];
         int min=array[0];
         for(int i=1;i<array.length;i++){
             if(array[i]>max){
                 max=array[i];
             }
             if(array[i]<min){
                 min=array[i];
             }

         }
        //创建计数数组
        int len=max-min+1;
        int[] count=new int[len];
        for(int j=0;j<array.length;j++){
            int index=array[j]-min;
            count[index]++;
        }
        int index=0;
        for(int m=0;m<len;m++){
            while(count[m]!=0){
                array[index]=m+min;
                index++;
                count[m]--;
            }
         }
    }
}
